#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm>
using namespace std;
void _quicksort(vector<int>& nums,int left,int right)
{
    if(left>right) return;
    int l=left-1;
    int r=right+1;
    int mid=rand()%(right-left+1)+left;
    int i=left;
    while(i<r)
    {
        if(nums[i]==nums[mid]) i++;
        else if(nums[i]>nums[mid]) swap(nums[i],nums[--r]);
        else swap(nums[i++],nums[++l]);
    }
    _quicksort(nums,left,l);
    _quicksort(nums,r,right);
}
void quicksort(vector<int>& nums,int n)
{
    srand(time(nullptr));
    _quicksort(nums,0,n);
}
int main()
{
    vector<int> arr({9,8,7,6,5,4,3,2,1});
    int n=arr.size()-1;
    quicksort(arr,n);
    for(auto e:arr)
    {
        cout<<e<<" "<<endl;
    }
    return 0;
}
